function Node(data) {
    this.data = data;
    this.next = null;
}

class MyLinkedList{
    constructor(){
        this.head = null;
        this.last = null;
        this.size = 0;
    }
    insert (index, data) {
        if (index < 0 || index > this.size) {
            throw new Error('超出链表节点范围!');
        }
        const insertedNode = new Node(data);
        if (this.size === 0) {
            // 空链表
            this.head = insertedNode;
            this.last = insertedNode;
        } else if (index === 0) {
            // 插入头部
            insertedNode.next = this.head
            this.head = insertedNode
        } else if (index === this.size) {
            // 插到尾部
            this.last.next = insertedNode;
            this.last = insertedNode;
        } else {
            // 插入到中间位置
            const prevNode = this.get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        this.size++;
    }
    remove (index) {
        if (index < 0 || index > this.size) {
            throw new Error('超出链表节点范围!')
        }
        let removedNode = null;
        if (index === 0) {
            // 删除头部
            removedNode = this.head;
            this.head = this.head.next;
        } else if (index === this.size - 1) {
            // 删除尾部
            const prevNode = this.get(index - 1)
            removedNode = this.last;
            prevNode.next = null;
            this.last = prevNode;
        } else {
            // 删除中间位置节点
            const prevNode = this.get(index-1);
            const nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode;
        }
        this.size--;
        return removedNode;
    }
    get(){
        if (index < 0 || index > this.size) {
            throw new Error('超出链表节点范围!')
        }
        const temp = this.head
        for (let i=0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }
    output() {
        let temp = this.head;
        while (temp!==null) {
            console.log(temp.data);
            temp = temp.next;
        }
    }
}

const myLinkedList = new MyLinkedList();
myLinkedList.insert(0,3);
myLinkedList.insert(0,4);
myLinkedList.insert(2,9);
myLinkedList.insert(3,5);
myLinkedList.insert(1,6);
myLinkedList.remove(0);
myLinkedList.output();